// https://www.acwing.com/problem/content/787/

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

// 三路快速排序的 partition 函数
// 将 nums[left..right] 区间划分为 <key、==key、>key 三部分
pair<int, int> partition(vector<int>& nums, int left, int right) {
    // 随机选择一个 pivot，避免最坏情况（退化为 O(n^2)）
    const int index = (int) random() % (right - left + 1) + left;
    swap(nums[index], nums[left]);  // 将 pivot 元素交换到最左边
    const int key = nums[left];     // 选定的划分值
    const int start = left;         // 保存最初的 left 位置
    int mid = start + 1;            // 当前遍历位置

    // left 用于追踪 < key 的边界
    // right 用于追踪 > key 的边界
    while (mid <= right) {
        if (nums[mid] < key) {
            // 小于 key，放到左边区域
            swap(nums[++left], nums[mid++]);
        } else if (nums[mid] > key) {
            // 大于 key，放到右边区域（注意 right-- 不移动 mid）
            swap(nums[mid], nums[right--]);
        } else {
            // 等于 key，不处理，mid 向右移动
            mid++;
        }
    }

    // 把 pivot 元素放到等于 key 的区间最左端
    swap(nums[left], nums[start]);

    // 返回等于 key 的区间起止位置：{left, right}
    return {left, right};
}

// 快速排序主函数：递归调用三路快排
void quick_sort(vector<int>& nums, int left, int right) {
    if (left < right) {
        auto p = partition(nums, left, right); // 划分
        quick_sort(nums, left, p.first - 1);   // 递归处理 < key 区间
        quick_sort(nums, p.second + 1, right); // 递归处理 > key 区间
    }
}

int main() {
    int n;
    scanf("%d", &n); // 输入数组大小
    vector<int> nums(n);

    // 输入数组元素
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 快速排序
    quick_sort(nums, 0, n - 1);

    // 输出排序结果
    for (const int num : nums) {
        printf("%d ", num);
    }
    return 0;
}
